package implement

import (
	"fmt"
)

type LRUCache1 struct {
	capacity int
	cache    map[int]int // 存储键值对
	keys     []int       // 存储访问顺序的键
}

// NewLRUCache1 创建一个新的 LRU 缓存
func NewLRUCache1(capacity int) *LRUCache1 {
	return &LRUCache1{
		capacity: capacity,
		cache:    make(map[int]int),
		keys:     make([]int, 0, capacity),
	}
}

// Get 从缓存中获取给定键的值。如果键不存在，返回 -1
func (lru *LRUCache1) Get(key int) int {
	if value, ok := lru.cache[key]; ok {
		lru.moveToFront(key) // 将访问的键移动到最前面
		return value
	}
	return -1
}

// Put 将键值对插入到缓存中
// 如果缓存已满，则移除最久未使用的键值对
func (lru *LRUCache1) Put(key, value int) {
	if _, ok := lru.cache[key]; ok {
		// 如果键已存在，更新值并将键移动到最前面
		lru.cache[key] = value
		lru.moveToFront(key)
		return
	}

	// 如果缓存已满，移除最久未使用的元素
	if len(lru.cache) == lru.capacity {
		// 移除数组中的最后一个元素，即最久未使用的键
		lru.removeOldest()
	}

	// 添加新键值对
	lru.cache[key] = value
	lru.keys = append([]int{key}, lru.keys...) // 在数组最前面插入新键
}

// moveToFront 将给定的键移动到 keys 数组的最前面
func (lru *LRUCache1) moveToFront(key int) {
	index := lru.findIndex(key)
	if index == -1 {
		return
	}
	// 删除原位置的键
	lru.keys = append(lru.keys[:index], lru.keys[index+1:]...)
	// 将键添加到最前面
	lru.keys = append([]int{key}, lru.keys...)
}

// removeOldest 移除 keys 数组中最后一个键值对（最久未使用的键）
func (lru *LRUCache1) removeOldest() {
	oldestKey := lru.keys[len(lru.keys)-1]
	// 从缓存和数组中删除最久未使用的键
	delete(lru.cache, oldestKey)
	lru.keys = lru.keys[:len(lru.keys)-1]
}

// findIndex 在 keys 数组中查找给定键的索引
func (lru *LRUCache1) findIndex(key int) int {
	for i, k := range lru.keys {
		if k == key {
			return i
		}
	}
	return -1
}

// Display 用于调试，打印缓存的键值对
func (lru *LRUCache1) Display() {
	for _, key := range lru.keys {
		fmt.Printf("%d:%d ", key, lru.cache[key])
	}
	fmt.Println()
}
